/*
 * @lc app=leetcode.cn id=330 lang=java
 *
 * [330] 按要求补齐数组
 */

// @lc code=start
class Solution {
    //这一天天的不是贪心就是dp，有毒吧。
    // 不过这个解法真的很巧妙，我是想不到的，而且感觉在做阅读理解+奥数。。
    public int minPatches(int[] nums, int n) {
        //注意是[1,n]这个区间内的。
        //每次找到未被数组 nums 覆盖的最小的整数 x
        //在数组中补充 x，然后寻找下一个未被覆盖的最小的整数，重复上述步骤直到区间 [1,n]中的所有数字都被覆盖。
        long x =1;//x可能超过int的最大值，故需要使用long
        int ans=0;
        int len = nums.length , index=0;
        while(x<=n){//x一直到n，或者大于n才算结束
            if(index<len && nums[index]<=x){//说明index还在nums[]数组的范围内
                x+=nums[index++];
            }else{//说明需要补充这个x，原来是[1,x-1]，补充之后[1,2x-1]都被覆盖
                x*=2;//现在[1,x-1]被覆盖
                ans++;
            }
        }
        return ans;
    }

}
// @lc code=end

